1. Field of the Invention
This invention relates to data compression. The invention relates particularly, but not exclusively, to the field of image data compression.
2. Description of the Prior Art
It has been proposed to provide an image data processing system in which image data are decorrelated into sub-band components, quantised and then entropy encoded. The quantisation provides some degree of data compression with some loss of information content. The subsequent entropy encoding effects a further degree of data compression with no loss of information content.
One known entropy encoding technique is so called run length encoding. A typical run length encoder looks for sequences of successive zeros within a data stream and assigns a code word to substitute for each sequence of zeros within the data stream. When the data stream is subsequently read, the run-length codes can be expanded to recreate the original data stream.
A variation on this arrangement is the type of run length encoding proposed in the standard being devised by the Joint Photographic Experts Group (JPEG) and currently under review by the International Standards Organisation. The JPEG standard proposes a run-length encoding technique in which a sequence of successive zero values terminated by a non-zero value is treated as an "event" and assigned a two-word run length code. The syntax of these two-word codes is: [RUNLENGTH, SIZE], [AMPLITUDE]. The RUNLENGTH variable specifies the number of zero values preceding the non-zero value. The SIZE variable specifies the number of bits that will be required to represent the amplitude of the non-zero value that terminates the sequence of successive zero values. The AMPLITUDE variable specifies the amplitude of the non-zero value.
Once the image data has been subjected to this run length encoding, it is then subjected to Huffman encoding. Huffman encoding is a form of commaless encoding whereby events are mapped to a set of codes having the property that no valid code is a prefix of a longer code. The most common events are mapped to the shortest Huffman codes.
An alternative encoding technique for the encoding of image signals has been proposed by P. Delogne and B. Macq in an article entitled "Universal Variable Length Coding for an Integrated Approach to Image Coding", published in Ann. Telecommun 46 7-8/1991). The authors describe a so-called "skip coding" technique for entropy encoding.
The skip coding technique will be described herein with reference to FIG. 1 which represents a sequence of image sample code words as a two-dimensional array represented in FIG. 1 of the accompanying drawings. In the two-dimensional array, the horizontal direction represents successive words for respective image samples, and the vertical axis represents the bits of each word from the least significant bit (LSB) position at the bottom (i.e. bit 0) to the most significant bit position (MSB) at the top (i.e. bit 11). In FIG. 1, the sample words for respective image pixels are represented as a one-dimensional stream. If, alternatively, they were represented two-dimensionally in terms of the rows and columns of a raster scanned image, the resulting array corresponding to FIG. 1 would be three dimensional, with the rows and columns forming two dimensions and the respective bits of each code word forming the third dimension. In FIG. 1, the cross-hatched bit positions represent non-zero bits and the blank bit positions represent zero bits. Words 0, 2, 3, 6, 7, 9, 10, 14, 15, 18, 20, 21 and 23 are assumed to represent words having only zero bits.
In accordance with the skip coding technique described in the aforementioned article, the array of sample words is then scanned as a sequence of bit runs from the most significant bit (MSB) position to the least significant bit position (LSB). However, the scanning does not access all bit positions in order. The scanning starts, for example at the top left hand position as illustrated in FIG. 1 (i.e. the left-hand side of the MSB position--bit 11 of word 0), and continues along the horizontal arrows A1.1, A1.2 until a non-zero bit is reached in a word, or until a predetermined maximum number m of zeros have been counted. At this point either a run length code for the number of zeros terminated by a one or for the run of m zeros is encoded. If a most significant non-zero bit in a word is encountered (eg. the bit 10 of word 8) the bits of this word are then output uncoded as represented by the vertical arrow A2 and word 8 is eliminated from the array. After the output of a word, or if a run of m zeros has been encoded, the scan restarts at the next bit in the scanning order (e.g. in FIG. 1 at bit 10 of word 9) and continues along the horizontal arrows A3.1, A3.2, A3.3 until a most significant non-zero bit in a further word is reached (in FIG. 1, bit 8 of word 19). Note in FIG. 1 that bit 8 of word 8 is skipped (hence the term applied to this type of coding) as by then that word has already been output and eliminated from the array. The bits of word 19 are then output uncoded as represented by the vertical arrow A4, the word 19 is eliminated from the array and the scanning restarts at the next bit position in the scanning order (in FIG. 1, bit 8 of word 20--horizontal arrow A5.1). This process continues until the last bit in the block (bit 0 of word 23) is reached.
The coding process proposed in this article does provide for relatively efficient coding of data samples. However, it does have a number of disadvantages. As the compression encoding employs bit-based encoding, it must operate at a faster rate than word-based encoders. Accordingly, a hardware implementation is more suited to meeting the high processing frequency requirements. However, as the coding method requires the coding process to switch repeatedly between run length encoding and the output of the bits of a word in uncoded form, this complicates the hardware implementation of the technique. Also, where data (e.g. image data) are to be stored or transmitted in a manner which provides a shuttle mode, a marker flag must be set against a word position when a most significant non-zero bit in a word is met and the remaining lower bits appended thereto in order for the skipping process to work. In the case of a digital video tape recorder, for example, where the data for recording are formatted in recording blocks, the coding will inevitably be split across those recording blocks. Then, if a recording block preceding a desired recording block is not retrieved on replay, it may be impossible to know where the marker flags have been set with the result that the replay decoder will not be able to restore the recorded data.